package com.mccken.practice.algorithm.tree_01;

import com.mccken.practice.algorithm.common.TreeNode_Common;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2023-12-12 20:04
 **/
public class TreeOperate {

	/**
	 * 判断两颗BST是否相同
	 *
	 * @param root1
	 * @param root2
	 * @return
	 */
	public static boolean isSameTree(TreeNode_Common root1, TreeNode_Common root2) {
		// 1. 空树
		if (root1 == null && root2 == null) {
			return true;
		}

		// 2. 其中一个是空树
		if (root1 == null || root2 == null) {
			return false;
		}

		// 3. 都不为空
		if (root1.val != root2.val) {
			return false;
		}

		return isSameTree(root1.left, root2.left) && isSameTree(root1.right, root2.right);
	}

	/**
	 * 判断BST是否合法
	 */
	public static boolean isValidBST(TreeNode_Common root) {
		return isValidBST(root, null, null);
	}

	private static boolean isValidBST(TreeNode_Common root, TreeNode_Common min, TreeNode_Common max) {
		if (root == null) {
			return true;
		}

		if (min != null && root.val <= min.val) {
			return false;
		}

		if (max != null && root.val >= max.val) {
			return false;
		}

		return isValidBST(root.left, min, root)
				&& isValidBST(root.right, root, max);
	}

	/**
	 * 在BST中查找一个值是否存在
	 */
	public static boolean isInBST_Version_1(TreeNode_Common root, int target) {
		if (root == null) {
			return false;
		}

		if (root.val == target) {
			return true;
		}

		return isInBST_Version_1(root.left, target) || isInBST_Version_1(root.right, target);
	}

	/**
	 * 在BST中查找一个值是否存在
	 */
	public static boolean isInBST_Version_2(TreeNode_Common root, int target) {
		if (root == null) {
			return false;
		}

		if (root.val == target) {
			return true;
		}

		if (target > root.val) {
			return isInBST_Version_2(root.right, target);
		} else {
			return isInBST_Version_2(root.right, target);
		}
	}
	
	public static TreeNode_Common insertIntoBST(TreeNode_Common root, int val) {
		if (root == null) {
			return new TreeNode_Common(val);
		}
		
		// 如果已经存在了，则不需要再重新插入了，直接返回即可
		if (root.val == val) {
			return root;
		}
		
		// 如果val小于root.val，则插入到左子树
		if (val < root.val) {
			root.left = insertIntoBST(root.left, val);
		}
		
		// 如果val大于root.val，则插入到右子树
		if(val > root.val) {
			root.right = insertIntoBST(root.right, val);
		}
		return root;
	}
	
	public static TreeNode_Common deleteTreeNode(TreeNode_Common root, int key) {
		if (root == null) {
			return null;
		}
		
		if (root.val == key) {
			if (root.right == null) {
				return root.left;	
			}
			if(root.left == null) {
				return root.right;
			}

			// 对于第三种情况：有两个非空子节点, 找到右子树的最小值，替换当前节点的值，然后删除掉最小值节点的右子树
			TreeNode_Common minNode = getMin(root.right);
			root.val = minNode.val;
			deleteTreeNode(minNode.right, minNode.val);
		} else if(key < root.val) {
			deleteTreeNode(root.left, key);
		} else if (key > root.val) {
			deleteTreeNode(root.right,key);
		}
		return root;
	}

	private static TreeNode_Common getMin(TreeNode_Common root) {
		while(root.left != null) {
			root = root.left;
		}
		return root;
	}

	
}
